In recent years, the storage device called a solid state drive (SSD), which incorporates NAND flash memories, has come into use. More and more SSDs have been used in various apparatuses such as mobile terminals, notebook personal computers, enterprise servers, etc. The NAND flash memory is a semiconductor memory characterized by low cost and large storage capacity.
However, data must be erased from the NAND flash memory before new data is written to it. The number of times of rewriting (erasing) data in the NAND flash memory is limited (e.g., 1000 times at most). Further, data must be written in units pages (each being 2 KB, for example), and data must be erased in units of blocks (each being 1 MB, for example). To cope with these problems, various measures are taken in any storage device incorporating NAND flash memories in the form of an SSD (see, for example, A High Performance Controller for NAND Flash-based Solid State Disk (C. Park, NVSMW 2006, pp. 17-20)).
The SSD comprises a controller, a work memory and storage memories. The controller exchanges commands with a host (PC, for example). The storage memories are, for example, NAND flash memories, and stores data supplied from the host. The work memory is, for example, a SRAM or a DRAM. The work memory holds a logical/physical address conversion table for respective data pages, a logical/physical block address conversion table for respective data blocks, a free block list, and the like.
In the SSD, the main initiator of control is an access command issued by, and coming from, the host. First, the controller converts the address (logical address) of the host command to addresses (physical addresses) of the storage memories. The data in the storage memories is thereby accessed. This is because the data at an address in any NAND flash memory must be erased to write new data to the same address, thereby to rewrite data in the NAND flash memory.
If the logical/physical address conversion is controlled, exclusively in units of pages (each being 2 KB, for example), the logical/physical address conversion tables will be inevitably too large to be held in the work memory. Therefore, the data is written in units of blocks (each being 1 MB, for example) into the storage memories. In this case, the data is managed in units of blocks in the logical/physical block address conversion table for respective data blocks.
Any blocks in which data is entirely rendered invalid during the write control or the garbage collection are managed in the form of a list (i.e., free block list). While data is being written in units of pages or blocks, more write areas may be required. In this case, information about blocks is extracted from the free block list, thereby providing write areas.
The control described above can disperse rewrite circuits to respective addresses. Nonetheless, as NAND flash memories are more miniaturized in the future, the number of times the data is rewritten will decrease. It is therefore necessary to control the data writing at higher efficiency. One method that may raise the efficiency of write control is to compress the data to be written to the NAND flash memories.
In Jpn. Pat. Appln. KOKAI Publication No. 2007-94639, for example, the controller first compresses the data supplied from the host and then stores the data into the NAND flash memories. The data transferred from the host to the NAND flash memories is thereby reduced in amount.
If the data is compressed in units of pages or blocks and then stored into the NAND flash memories, however, the storage area thereby rendered free will be wasted. Further, if the data items are arranged on the basis of the sizes they have after having been compressed, the locations of the data items must be managed in minute units. Consequently, each entry in the conversion table will have a very large size. This makes it difficult to manage the data in the work memory. In addition, the data is erased only in units of blocks. From this point of view, since any data item may extend over a block boundary, the control complex will be complicated.